/**
 *
 * @author mary
 */
public class Sort {

    public void downHeap(int a[], int k, int n) {
        int new_elem;
        int child;
        new_elem = a[k];

        while (k <= n / 2) {
            child = 2 * k;

            if (child < n && a[child] < a[child + 1]) {
                child++;
            }
            if (new_elem >= a[child]) {
                break;
            }

            a[k] = a[child];
            k = child;
        }
        a[k] = new_elem;
    }

    void heapSort(int a[], int size) {
        int i;
        int temp;

        for (i = size / 2 - 1; i >= 0; i--) {
            downHeap(a, i, size - 1);
        }

        for (i = size - 1; i > 0; i--) {
            temp = a[i];
            a[i] = a[0];
            a[0] = temp;

            downHeap(a, 0, i - 1);
        }
    }

    public static void main(String[] args) {
        int[] a = {4, 55, 87, 43, 6, 84, 17, 90};
        Sort mas = new Sort();
        for (int i = 0; i < a.length; i++) {
            System.out.print(" " + a[i]);
            System.out.print(" ");
        }
        mas.heapSort(a, 8);
        System.out.println("");
        for (int i = 0; i < a.length; i++) {
            System.out.print(" " + a[i]);
            System.out.print(" ");
        }


    }
}
/*
 * Скорость работы Пирамидальной сортировки - O(n log n). Oбъем необходимой
 * дополнительной памяти = 0.
 */
